#include <iostream>
#include <vector>
#include <memory>
#include <algorithm>

//策略接口
class SortStrategy {
public:
    virtual void sort(std::vector<int>& data) = 0;
    virtual ~SortStrategy() = default;
};

//  具体策略：冒泡排序
class BubbleSort : public SortStrategy {
public:
    void sort(std::vector<int>& data) override {
        for (size_t i = 0; i < data.size(); ++i) {
            for (size_t j = 0; j + 1 < data.size() - i; ++j) {
                if (data[j] > data[j + 1]) {
                    std::swap(data[j], data[j + 1]);
                }
            }
        }
        std::cout << "BubbleSort used\n";
    }
};

//  具体策略：STL sort
class STLQuickSort : public SortStrategy {
public:
    void sort(std::vector<int>& data) override {
        std::sort(data.begin(), data.end());
        std::cout << "STL sort used\n";
    }
};

// 环境类（持有策略对象）
class Context {
private:
    std::unique_ptr<SortStrategy> strategy;
public:
    void setStrategy(std::unique_ptr<SortStrategy> s) {
        strategy = std::move(s);
    }

    void execute(std::vector<int>& data) {
        if (strategy) {
            strategy->sort(data);
        } else {
            std::cerr << "No strategy set!\n";
        }
    }
};

int main() {
    std::vector<int> nums = {5, 2, 9, 1, 3};

    Context ctx;

    // 切换到冒泡排序
    ctx.setStrategy(std::make_unique<BubbleSort>());
    ctx.execute(nums);

    for (int n : nums) std::cout << n << " ";
    std::cout << "\n";

    // 切换到 STL sort
    nums = {5, 2, 9, 1, 3};
    ctx.setStrategy(std::make_unique<STLQuickSort>());
    ctx.execute(nums);

    for (int n : nums) std::cout << n << " ";
    std::cout << "\n";

    return 0;
}
